package org.example.data_structure.tree;

/**
 * 二叉树
 * @author shenguangyang
 */
public class BinaryTreeExample {
    public static void main(String[] args) {
        // 创建二叉树
        MyNode node1 = new MyNode("node1");
        MyNode node2 = new MyNode("node2");
        MyNode node3 = new MyNode("node3");
        MyNode node4 = new MyNode("node4");
        MyNode node5 = new MyNode("node5");

        // 手动创建二叉树
        node1.left = node2;
        node1.right = node3;
        node3.left = node4;
        node3.right = node5;

        BinaryTree binaryTree = new BinaryTree(node1);
        System.out.println("==========================> preOrder");
        binaryTree.preOrder();
        System.out.println("\n==========================> midOrder");
        binaryTree.midOrder();
        System.out.println("\n==========================> postOrder");
        binaryTree.postOrder();
    }

    private static class BinaryTree {
        private final MyNode root;

        public BinaryTree(MyNode root) {
            if (root == null) {
                throw new RuntimeException("root不能为空");
            }
            this.root = root;
        }

        /**
         * 前序遍历
         */
        public void preOrder() {
            this.root.preOrder();
        }

        public void midOrder() {
            this.root.midOrder();
        }

        public void postOrder() {
            this.root.postOrder();
        }
    }

    private static class MyNode {
        String name;
        MyNode left;
        MyNode right;

        public MyNode(String name) {
            this.name = name;
        }

        // 前序遍历
        public void preOrder() {
            // 先输出父几点
            System.out.print(this);
            // 递归向左子树前序遍历
            if (this.left != null) {
                this.left.preOrder();
            }
            // 递归向右子树前序遍历
            if (this.right != null) {
                this.right.preOrder();
            }
        }

        // 中序遍历
        public void midOrder() {
            // 递归向左子数据进行中序遍历
            if (this.left != null) {
                this.left.midOrder();
            }
            // 输出父节点
            System.out.print(this);
            // 递归向右子数据中序遍历
            if (this.right != null) {
                this.right.midOrder();
            }
        }

        // 后续遍历
        public void postOrder() {
            if (this.right != null) {
                this.right.postOrder();;
            }
            if (this.left != null) {
                this.left.postOrder();
            }
            System.out.print(this);
        }

        @Override
        public String toString() {
            return name + " ";
        }
    }
}
